from typing import List


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        ans = 0
        m = len(obstacleGrid)
        if m <= 0:
            return ans
        n = len(obstacleGrid[0])
        if n <= 0:
            return ans
        if m == 1 and n == 1 and obstacleGrid[0][0] == 1:
            return ans
        # 二维数组
        # dp = [[0 for i in range(n)] for j in range(m)]
        # dp[0][0] = 1
        # for i in range(m):
        #     for j in range(n):
        #         if obstacleGrid[i][j] == 0:
        #             if i > 0 and obstacleGrid[i-1][j] == 0:
        #                 dp[i][j] += dp[i-1][j]
        #             if j > 0 and obstacleGrid[i][j-1] == 0:
        #                 dp[i][j] += dp[i][j-1]
        # ans = dp[m-1][n-1]
        dp = [[0 for i in range(n)] for j in range(2)]
        dp[0][0] = 1
        for j in range(1, n):
            if obstacleGrid[0][j] == 0 and obstacleGrid[0][j-1] == 0:
                dp[0][j] += dp[0][j-1]
        i0, i1 = 0, 1
        for i in range(1, m):
            for j in range(n):
                dp[i1][j] = 0
                if obstacleGrid[i][j] == 0:
                    if obstacleGrid[i-1][j] == 0:
                        dp[i1][j] += dp[i0][j]
                    if j > 0 and obstacleGrid[i][j-1] == 0:
                        dp[i1][j] += dp[i1][j-1]
            i0, i1 = i1, i0
        ans = dp[i0][n-1]
        return ans


solve = Solution()
questions = [
    ([[0, 0, 0], [0, 1, 0], [0, 0, 0]],),
    ([[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0]],),
]

for qi, q in enumerate(questions, 1):
    grid, = q
    print(f'#{qi}:', grid)
    print(' ans:', solve.uniquePathsWithObstacles(grid))

